package com.leetcode.partition5;

import java.util.PriorityQueue;
import java.util.TreeSet;

/**
 * @author `RKC`
 * @date 2021/10/6 9:11
 */
public class LC414第三大的数 {

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    public static int thirdMax(int[] nums) {
        return priorityQueue(nums);
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2};
        System.out.println(thirdMax(nums));
    }

    @SuppressWarnings("ConstantConditions")
    private static int priorityQueue(int[] nums) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(DEFAULT_INITIAL_CAPACITY, (o1, o2) -> Integer.compare(o2, o1));
        for (int num : nums) {
            heap.add(num);
        }
        if (nums.length < 3) return heap.peek();
        int deleteCount = 0, prev = Integer.MIN_VALUE, maxValue = heap.peek();
        while (deleteCount < 3) {
            if (heap.isEmpty()) return maxValue;
            if (prev == heap.peek()) deleteCount--;
            prev = heap.poll();
            deleteCount++;
        }
        return prev;
    }

    private static int treeSet(int[] nums) {
        //有序集合，使用TreeSet维护一个前三大的数
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) {
            set.add(num);
            if (set.size() > 3) {
                set.pollFirst();
            }
        }
        return set.size() == 3 ? set.first() : set.last();
    }
}
